package com.datastructure.test.pathsumofroottoleaf;

import java.util.ArrayList;
import java.util.Stack;

public class PathSumOfRootToLeaf {

    ArrayList<ArrayList<Integer>> data = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left=new TreeNode(2);
        treeNode.right=new TreeNode(3);
        PathSumOfRootToLeaf pathSumOfRootToLeaf = new PathSumOfRootToLeaf();
        int i = pathSumOfRootToLeaf.sumNumbers(treeNode);
        System.out.println(i);
    }

    public int sumNumbers (TreeNode root) {
        // 调用dfs
        return dfs(root,0);
    }
    //深度优先搜索
    public int dfs(TreeNode root,int sum){
        if(root==null){
            return 0;
        }
        int total = sum*10+root.val;
        //已达到叶子节点，返回结果
        if(root.left==null && root.right==null){
            return total;
        }else{
            //递归调用
            return dfs(root.left,total)+dfs(root.right,total);
        }
    }

    public int sumNumbers1 (TreeNode root) {
        //如果根节点是空，直接返回0即可
        if (root == null)
            return 0;
        //两个栈，一个存储的是节点，一个存储的是节点对应的值
        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> valueStack = new Stack<>();
        //全局的，统计所有路径的和
        int res = 0;
        nodeStack.add(root);
        valueStack.add(root.val);
        while (!nodeStack.isEmpty()) {
            //当前节点和当前节点的值同时出栈
            TreeNode node = nodeStack.pop();
            int value = valueStack.pop();
            if (node.left == null && node.right == null) {
                //如果当前节点是叶子结点，说明找到了一条路径，把这条
                //路径的值加入到全局变量res中
                res += value;
            } else {
                //如果不是叶子节点就执行下面的操作
                if (node.right != null) {
                    //把子节点和子节点的值分别加入到栈中，这里子节点的值
                    //就是父节点的值*10+当前节点的值
                    nodeStack.push(node.right);
                    valueStack.push(value * 10 + node.right.val);
                }
                if (node.left != null) {
                    nodeStack.push(node.left);
                    valueStack.push(value * 10 + node.left.val);
                }
            }
        }
        return res;
    }
}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
